/*
 * @lc app=leetcode.cn id=850 lang=cpp
 *
 * [850] 矩形面积 II
 */
#include "include.h"
// @lc code=start

struct LeafNode;
// segtree node is just a range [start, end)
struct SegTreeNode
{
    // [start, end)
    int start, end;

    SegTreeNode *left, *right;
    LeafNode* leafPtr = nullptr;
    SegTreeNode() : start(0), end(0), left(nullptr), right(nullptr){}
    SegTreeNode(int from, int to) : start(from), end(to), left(nullptr), right(nullptr){}
    SegTreeNode(int from, int to, int tracked) : start(from), end(to), left(nullptr), right(nullptr){}
};
// put data into leaf
struct LeafNode
{
    SegTreeNode* segTreePtr;
    // LeafNode* prev;
    LeafNode* next;
    
    // <y, delta>
    std::map<int, int> columnInfo;
    LeafNode() : segTreePtr(nullptr), next(nullptr) {}
    LeafNode(SegTreeNode* infoPtr) : segTreePtr(infoPtr), next(nullptr) {}
};

class axisManager {
public:
    SegTreeNode* root_;
    LeafNode* leafHead_;
public:
    axisManager() {
        root_ = new SegTreeNode(0, 1e9);
        leafHead_ = new LeafNode(root_);
        root_->leafPtr = leafHead_;
    }
    ~axisManager() {
        clearTree(root_);
        clearList(leafHead_);
    }
public:
    // return : seg => x ~ [start, end)
    SegTreeNode* split(int x) {
        SegTreeNode* root = findBelongingLeft(x, root_);
        if (x == root->start) {return root;}
        // if (x == root->end) {return root->leafPtr->next->segTreePtr;}

        root->left = new SegTreeNode(root->start, x);
        root->right = new SegTreeNode(x, root->end);

        // use origin as left
        LeafNode* origin = root->leafPtr;
        // use new one as right
        LeafNode* temp = new LeafNode(root->right);
        // share same column info
        temp->columnInfo = origin->columnInfo;

        temp->next = origin->next;
        origin->next = temp;
        origin->segTreePtr = root->left;
        // temp->segTreePtr = root->right;

        root->leafPtr = nullptr;
        root->left->leafPtr = origin;
        root->right->leafPtr = temp;

        return root->left;
    }
    // return : start <= x < end, default from root
    SegTreeNode* findBelongingLeft(int x) {
        return findBelongingLeft(x, root_);
    }
    // return : start < x <= end, default from root
    SegTreeNode* findBelongingRight(int x) {
        return findBelongingRight(x, root_);
    }
private:
    // return : start <= x < end
    SegTreeNode* findBelongingLeft(int x, SegTreeNode* root){
        if (root->left and root->right){
            if (x < root->right->start){return findBelongingLeft(x, root->left);}
            else {return findBelongingLeft(x, root->right);}
        }else{
            return root;
        }
    }
    // return : start < x <= end
    SegTreeNode* findBelongingRight(int x, SegTreeNode* root){
        if (root->left and root->right){
            if (x <= root->right->start){return findBelongingRight(x, root->left);}
            else {return findBelongingRight(x, root->right);}
        }else{
            return root;
        }
    }
private:
    void clearTree(SegTreeNode* root){
        // post order traverse
        if (root->left){clearTree(root->left);}
        if (root->right){clearTree(root->right);}
        // do
        delete root;
    }
    void clearList(LeafNode* leaf){
        if (!leaf) {return;}
        clearList(leaf->next);
        delete leaf;
    }
};

class Solution {
public:
    int rectangleArea(vector<vector<int>>& rectangles) {
        long long res = 0;

        axisManager x_axis;

        for (int i=0;i<rectangles.size();++i){
            int left = rectangles[i][0];
            int bottom = rectangles[i][1];
            int right = rectangles[i][2];
            int top = rectangles[i][3];

            // todo : need optimize here
            x_axis.split(left);
            x_axis.split(right);

            auto rightBelonging = x_axis.findBelongingRight(right)->leafPtr;
            auto leftBelonging = x_axis.findBelongingLeft(left)->leafPtr;

            for (auto leafPtr=leftBelonging;leafPtr!=rightBelonging->next;leafPtr=leafPtr->next) {
                leafPtr->columnInfo[bottom] += 1;
                leafPtr->columnInfo[top] -= 1;
            }
        }

        auto leafPtr = x_axis.leafHead_;

        while (leafPtr) {
            auto& columnDelata = leafPtr->columnInfo;
            
            int z_height = 0;
            int y_start = 0;
            int y_end = 0;

            // sum column ~
            for (auto& delta : columnDelata) {
                int y = delta.first;

                int z_before = z_height;
                z_height += delta.second;
                int z_after = z_height;

                if (z_before == 0 and z_after > 0) {
                    y_start = y;
                }
                if (z_before > 0 and z_after == 0) {
                    y_end = y;
                    res += static_cast<long long>(y_end - y_start) * 
                           static_cast<long long>(leafPtr->segTreePtr->end - leafPtr->segTreePtr->start);
                }
            }
            
            leafPtr = leafPtr->next;
        }

        return res % 1000000007;
    }
};
// @lc code=end

